#include "main.h"

void create_tree(BiTreeNode** root_pp, char* pre_order_seq, int num_elements) {
    // 初始化整棵树的根节点
    static int num_element = -1;
    num_element++;
    if (pre_order_seq[num_element] != '\0' && pre_order_seq[num_element] != '#') {
        (*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*root_pp)->data = pre_order_seq[num_element];
        create_tree(&((*root_pp)->leftChild), pre_order_seq, num_elements);
        create_tree(&((*root_pp)->rightChild), pre_order_seq, num_elements);
    }
    else {
        (*root_pp) = 0;
    }

    // 使用合适的参数调用上面定义的 _recur_create_tree 函数
}


// 递归地销毁由*root指向根节点的树：释放该树所被动态分配的内存空间
void destroy(BiTreeNode** root)
{
    if ((*root) != 0) {
        destroy(&((*root)->leftChild));
        destroy(&((*root)->rightChild));
        free(*root);
    }
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode* t, void visit(DataType item))
{
    if (t != 0) {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);

    }

}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode* t, void visit(DataType item))
{
    if (t != 0) {
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode* t, void visit(DataType item))
{
    if (t != 0) {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
}

// 请实现此函数
// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode* search(BiTreeNode* root, DataType x)
{
    if (root == 0) {
        return NULL;
    }
    else if ((root->data) == x) {
        return root;
    }
    BiTreeNode* a = search(root->leftChild, x);
    BiTreeNode* b = search(root->rightChild, x);
    if (a != NULL) {
        return a;
    }
    else {
        return b;
    }
}

void visit(DataType item)
{
    printf("%c ", item);
}


int main(void)
{
    void (*p)(DataType item) = visit;
    BiTreeNode* treeNode = 0;
    char letter = 'A';
    create_tree(&treeNode, "ABC##DE#G##F###", 7);
    pre_order_traverse(treeNode, p);
    printf("%p", search(treeNode, letter));
    destroy(&treeNode);
    return 0;
}